package org.ns.summer.classpath.scan.prefix;

import java.util.HashMap;
import java.util.Map;

/**
 * 2020-03-30
 * 前缀树，用来快速匹配前缀
 */
public class PrefixTree { // 前缀树

    private Node head = new Node(' ');

    public static PrefixTree create(String... values) {
        PrefixTree prefixTree = new PrefixTree();
        prefixTree.adds(values);
        return prefixTree;
    }

    private static class Node {
        private char c;
        private boolean end;
        private Map<Character, Node> nexts = new HashMap<>();

        Node(char c) {
            this.c = c;
        }
        Node getOrCreate(char c) {
            Node node = nexts.get(c);
            if (node == null) {
                node = new Node(c);
                nexts.put(c, node);
            }
            return node;
        }
        Node next(char c) {
            Node node = nexts.get(c);
            return node;
        }

        void setEnd(boolean end) {
            this.end = end;
        }

        boolean isEnd() {
            return end;
        }
    }
    public void adds(String... values) {
        for (String value : values) {
            add(value);
        }
    }
    public void add(String value) {
        if (value == null || value.isEmpty()) {
            return;
        }

        Node node = head;
        for(int i = 0;i < value.length(); i++) {
            char c = value.charAt(i);
            node = node.getOrCreate(c);
        }
        node.setEnd(true);
    }

    public boolean match(String value) { // 匹配前缀
        if (value == null || value.isEmpty()) {
            return true;
        }
        Node node = head;
        for(int i = 0;i < value.length(); i++) {
            char c = value.charAt(i);
            node = node.next(c);
            if (node == null) {
                return false;
            } else if (node.isEnd()) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        PrefixTree prefixTree = new PrefixTree();
        prefixTree.adds("asd","dfdfd","2423", "ffss");

        System.out.println(prefixTree.match("asdffdfd"));
        System.out.println(prefixTree.match("dfdfdffcc"));
        System.out.println(prefixTree.match("2423fcv"));
        System.out.println(prefixTree.match("ffss43fds"));

        System.out.println(prefixTree.match("2ffdf2423fcvdasdffdfd"));
        System.out.println(prefixTree.match("a2sdfffssfdf2423fcvdasdffdfd"));
    }
}
